/**
 * Created by JiaJia on 2019/5/23 0023.
 * 矩阵中的路径
 * 用回溯的思想求解
 * 标记已经走过的格子，判断后需要重置状态
 */
public class Code66 {
    public boolean hasPath(char[] matrix, int rows, int cols, char[] str)
    {
        int[] flag=new int[matrix.length];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j <cols ; j++) {
                if (helper(matrix,rows,cols,i,j,str,0,flag))
                return true;
            }
        }
        return false;
    }
    private boolean helper(char[] matrix,int rows, int cols, int i,int j,char[] str,int k,int[] flag){
        int index=i*cols+j;
        if (i<0||i>=rows||j<0||j>=cols||matrix[index]!=str[k]||flag[index]==1){
            return false;
        }
        if (k==str.length-1){
            return true;
        }
        flag[index]=1;
        if (helper(matrix,rows,cols,i-1,j,str,k+1,flag)
                ||helper(matrix,rows,cols,i+1,j,str,k+1,flag)
                ||helper(matrix,rows,cols,i,j-1,str,k+1,flag)
                ||helper(matrix,rows,cols,i,j+1,str,k+1,flag)){
            return true;
        }
        flag[index]=0;
        return false;
    }
}